package org.algorithm.二师兄.链表;

import org.algorithm.common.ListNode;
import org.junit.Test;

/**
 * @author
 * @Date 2022/2/22
 * @Link {https://leetcode-cn.com/problems/SLwz0R/}
 */
public class 删除链表的倒数第n个结点 {


    @Test
    public void test() {
        ListNode listNode = removeNthFromEnd(org.algorithm.common.ListNode.build(1,2,3,4,5), 2);
        org.algorithm.common.ListNode.print(listNode);
    }

    public ListNode removeNthFromEnd(org.algorithm.common.ListNode head, int n) {
        // 快慢指针寻找中间节点
        /***
         *  1. 快指针移动N位,
         *  2. 快指针的next如果不为空， 则慢指针走一步
         *  3. 快指针next为空， 慢指针走两步,  快指针到头后， 慢指针走到中间， 快慢中间距离就是N
         */

        // 哨兵节点， 链接头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        // 快指针先走两步
        for (int i = 0; i < n - 1; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            if (fast.next == null) {
                slow = slow.next.next;
                break;
            }else {
                slow = slow.next;
            }
        }
        return  dummy.next;
    }
}
